package org.dlx.common;

import java.util.ArrayList;

//最小堆排序
public class HeapSorter
{
    private ArrayList<Integer> _heap = new ArrayList<>();

    public int push(Integer entry){
        int index = _heap.size();
        _heap.add(entry);
        return upHeap(index);
    }

    public Integer pop(){
        if(_heap.size() <= 0) {
            return null;
        }
        Integer entry = _heap.get(0);
        removeHead();
        return entry;
    }

    //删除头节点 头节点删除要先跟尾结点交换
    private void removeHead(){
        if(_heap.size() <= 0){
            return;
        }
        if(_heap.size() == 1) {
            _heap.remove(0);
            return;
        }
        int tail = _heap.size() - 1;
        swap(tail, 0);//交换尾节点
        _heap.remove(tail);
        //要准备下滤
        downHeap(0);
    }
    //准备下滤 最小堆要保证父节点比子节点小
    private int downHeap(int index){
        int child = getLChildIndex(index);
        while(child < _heap.size()){
            int rchild = getRSiblingIndex(child);
            //右兄弟有效且比左 小 则最小子是右
            int minChild = rchild < _heap.size() && _heap.get(rchild) < _heap.get(child) ? rchild : child;
            swap(minChild, index);
            index = minChild;
            child = getLChildIndex(index);
        }
        return index;
    }

    //添加节点上滤
    private int upHeap(int index){
        int parent = getParentIndex(index);
        while(index > 0 && _heap.get(parent) < _heap.get(index)){
            swap(parent, index);//交换父和子
            index = parent;
            parent = getParentIndex(index);
        }
        return index;
    }

    private void swap(int left, int right){
        Integer litem = _heap.get(left);
        Integer ritem = _heap.get(right);
        _heap.set(left, ritem);
        _heap.set(right, litem);
    }
    //得到父索引
    private int getParentIndex(int i){
        return (i - 1) / 2;
    }
    //得到子索引
    private int getLChildIndex(int i) {
        return 2 * i + 1;
    }
    //得到兄弟索引
    private int getRSiblingIndex(int i){
        return i + 1;
    }
}
